package com.data.construct.multiTree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 层序遍历多叉树
 * BFS(Breadth-First Search)，即广度优先搜索
 *
 * @author sunhl
 * @Description:
 * @Date: created in 2024/11/12 0012 11:01
 * @Modified By:
 */
public class BFSMultiTree {

    /**
     * 简单写法
     * 每次把队头元素拿出来，然后把它的子节点加入队列，就完事了。
     * 缺点是，无法知道当前节点在第几层。
     * <p>
     * 也因此这种写法用的不多
     *
     * @param root
     */
    void levelOrderTraverse1(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> q = new LinkedList<>();

        q.offer(root);

        while (!q.isEmpty()) {
            Node cur = q.poll();
            // 访问 cur 节点
            System.out.println(cur.val);

            // 把 cur 的子节点加入队列
            for (Node child : cur.children) {
                q.offer(child);
            }
        }
    }

    /**
     * 最常用写法
     * 对上面方法稍作改造, 主要是记录了遍历节点所在的层数
     * 可以解决诸如多叉树最小深度这样的问题，是我们最常用的层序遍历写法。
     *
     * @param root
     */
    void levelOrderTraverse2(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        // 记录当前遍历到的层数（根节点视为第 1 层）
        int depth = 1;

        while (!q.isEmpty()) {
            int sz = q.size();

            for (int i = 0; i < sz; i++) {
                Node cur = q.poll();
                // 访问 cur 节点，同时知道它所在的层数
                System.out.println("depth = " + depth + ", val = " + cur.val);

                for (Node child : cur.children) {
                    q.offer(child);
                }
            }

            depth++;
        }
    }

    /**
     * 写法三
     * 让每一个节点在遍历过程中, 可以维护自己的路径权重和
     * 每个节点都有了自己的 depth 变量，是最灵活的，可以满足所有 BFS 算法的需求
     * 节点需要被State包一层, 再往队列中放
     * 这种边带有权重的场景属于图结构算法，在之后的BFS 算法习题集 和 dijkstra 算法 中，才会用到这种写法。
     *
     * @param root
     */
    void levelOrderTraverse3(Node root) {
        if (root == null) {
            return;
        }
        Queue<State> q = new LinkedList<>();
        // 记录当前遍历到的层数（根节点视为第 1 层）
        q.offer(new State(root, 1));

        while (!q.isEmpty()) {
            State state = q.poll();
            Node cur = state.node;
            int depth = state.depth;
            // 访问 cur 节点，同时知道它所在的层数
            System.out.println("depth = " + depth + ", val = " + cur.val);

            for (Node child : cur.children) {
                q.offer(new State(child, depth + 1));
            }
        }
    }
}
